1. Technical Field
The present invention generally relates to removal of elements from a linked list. In particular, the present invention provides apparatus and methods for removing elements from a linked list while allowing access to other elements of the linked list during the removal.
2. Description of Related Art
In data management, a linked list is a group of items, each of which contains a pointer to the next item. A linked list allows for the organization of a set of data in noncontiguous storage locations. Linked lists are used in many types of computing environments and are used for the management of various types of data.
One computing environment in which linked lists may be utilized is a multiprocessor system. In a multiprocessor system a plurality of processors may attempt accesses and/or modifications to elements in the linked list at substantially the same time. Thus, there is a system of locks utilized to make sure that only a single processor may access and/or modify a particular element in the linked list at one time. If such a mechanism were not used, two or more different processors may perform conflicting actions on the linked list element or the action of one processor on the linked list element may be negatively impacted by the actions performed by the other processors.
This problem is further exacerbated when elements need to be removed from the linked list, e.g., elements that are no longer being used by any of the processors (garbage collection). It is important, however, during such removal of elements of a linked list in a multiprocessor system, that elements are not modified or removed that are or may be utilized by one or more of the processors during the removal process.
In known mechanisms for removal of elements in a linked list, the list is protected from any changes at all times during the removal process. Such an approach has the disadvantage that it will synchronize all accesses to the list, making multiprocessor use of the list prohibitively slow. Another common way of handling such removal of elements is to have a second linked list that maintains elements to be freed, i.e. deferred freeing of the elements, and free the entire second list at once. Unfortunately, this implementation requires the element be removed from the first list by, again, locking the linked list and adjusting pointers in the linked list elements to remove the element. Thus, in all known mechanisms for removing elements from a linked list, a lock of the linked list is required and serialization of accesses to the linked list results.
Therefore, it would be beneficial to have an apparatus and method for removing elements from a linked list that allows access to elements of the linked list during removal of other elements of the linked list. In this way, serialization of accesses to the linked list are avoided.